package simple.string;

/**
 * <a href="https://leetcode.cn/problems/repeated-substring-pattern/">459. 重复的子字符串</a>
 * 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
 * 示例 1:
 *   输入: s = "abab"
 *   输出: true
 *   解释: 可由子串 "ab" 重复两次构成。
 * 示例 2:
 *   输入: s = "aba"
 *   输出: false
 * 示例 3:
 *   输入: s = "abcabcabcabc"
 *   输出: true
 *   解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
 * 提示：
 *   1 <= s.length <= 10^4
 *   s 由小写英文字母组成
 * @author 刘学松
 * @date 2023-05-15 16:39
 */
public class 重复的子字符串 {
    public static void main(String[] args) {
        System.out.println(test("abcabcabcabcabc"));
    }
    public boolean repeatedSubstringPattern(String s) {
        if (s.length() == 1) {
            return false;
        }
        char c = s.charAt(0);
        int fromIndex = 1, i=0, midIndex = s.length() >> 1;
        while (i < midIndex && i!=-1) {
            i = s.indexOf(c, fromIndex);
            fromIndex = i+1;
            if (i==-1||s.length() % i != 0) {
                continue;
            }
            int from = i, left = 0;
            while (from < s.length()) {
                if (left == i) {
                    left = 0;
                }
                if (s.charAt(left) != s.charAt(from)) {
                    break;
                }
                left++;
                from++;
            }
            if (from == s.length()) {
                return true;
            }
        }
        return false;
    }

    public static boolean test(String s) {
        int len = s.length();
        int n = len;
        int count = 2;
        while (n > 1) {
            if (n % count == 0) {
                int k = len / count;
                if (s.substring(0, len - k).equals(s.substring(k))) {
                    return true;
                }
                while (n % count == 0) {
                    n /= count;
                }
            }
            count++;
        }
        return false;
    }
}
